/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-09-09
 * Time: 14:23
 */
class ListNode{
    int data;
    ListNode prev;
    ListNode next;
    ListNode(int data){
        this.data=data;
        this.prev=null;
        this.next=null;
    }
}
public class MyDoubleLinkedList {
    ListNode head;
    ListNode tail;
    MyDoubleLinkedList(){
        this.head=null;
        this.tail=null;
    }


    public void display(){
        ListNode cur=this.head;
        if(cur==null){
            System.out.println("链表为空");
            return;
        }
        while(cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    public int size(){
        int count=0;
        ListNode cur=this.head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public boolean contains(int key){
        ListNode cur=this.head;
        while(cur!=null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    public void addFirst(int data){
        ListNode temp=new ListNode(data);
        if(this.head==null){
            this.head=this.tail=temp;
            return ;
        }
        temp.next=head;
        head.prev=temp;
        head=temp;
    }

    public void addLast(int data){
        ListNode temp=new ListNode(data);
        if(this.head==null){
            this.head=this.tail=temp;
            return ;
        }
        tail.next=temp;
        temp.prev=tail;
        tail=temp;
    }

    //删除数据为key 的节点
    public void removeKey(int key){
        ListNode cur=this.head;
        while(cur!=null){
            if(cur.data==key){
                if(cur==this.head){
                    this.head=head.next;
                    if(head==null){
                        this.tail=null;
                    }else{
                        this.head.prev=null;
                    }
                }else{
                    if(cur==this.tail){
                        this.tail=this.tail.prev;
                        this.tail.next=null;
                    }else{
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
                return;
            }
            cur=cur.next;
        }
        System.out.println("未找到");
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur=this.head;
        while(cur!=null){
            if(cur.data==key){
                if(cur==this.head){
                    this.head=head.next;
                    if(head==null){
                        this.tail=null;
                    }else{
                        this.head.prev=null;
                    }
                }else{
                    if(cur==this.tail){
                        this.tail=this.tail.prev;
                        this.tail.next=null;
                    }else{
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
            }
            cur=cur.next;
        }
    }

    public ListNode searchIndex(int index){
        int count=index;
        ListNode cur=this.head;
        while(count!=0){
            cur=cur.next;
            count--;
        }
        return cur;
    }

    public void addIndex(int index, int data){
        if(index<0||index>this.size()-1){
            System.out.println("下标不在正确范围");
            return;
        }
        ListNode cur=this.searchIndex(index);
        if(cur==head){
            this.addFirst(data);
            return;
        }else if(cur==tail){
            this.addLast(data);
            return;
        }
        ListNode temp=new ListNode(data);
        temp.prev=cur.prev;
        cur.prev.next=temp;
        temp.next=cur;
        cur.prev=temp;
        return;
    }

    public void clear(){
        ListNode cur=this.head;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=null;
            cur.prev=null;
            cur=curNext;
        }
        this.head=null;
        this.tail=null;
    }
}
